package com.datastructure.test.maxdepthofbinarytree;

import java.util.LinkedList;

public class MaxDepthOfBinaryTree {

    public static void main(String[] args) {

    }

    public int getMaxDepthOfBinaryTree(TreeNode root){
        if(root == null){
            return 0;
        }
        int max = 0;
        if(root.left!=null){
            max = Math.max(max,getMaxDepthOfBinaryTree(root.left));
        }
        if(root.right!=null){
            max = Math.max(max,getMaxDepthOfBinaryTree(root.right));
        }
        return max+1;
    }

    public int run (TreeNode root) {
        // 一些特殊情况的处理
        if (null == root) {
            return 0;
        }
        if (null == root.left && null == root.right) {
            return 1;
        }
        // 具体代码实现
        return getMinDepthOfBinaryTree(root);
    }

    public int getMinDepthOfBinaryTree(TreeNode root){
        if(root == null){
            return 0;
        }
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        if(root.left!=null){
            min1 = Math.min(min1,getMinDepthOfBinaryTree(root.left));
        }
        if(root.right!=null){
            min2 = Math.min(min2,getMinDepthOfBinaryTree(root.right));
        }
        return Math.min(min2,min1);
    }

    //非递归
    public static int getMaxDeep(TreeNode root){
        if(root == null) return 0;
        int deepth = 0; //深度
        LinkedList<TreeNode> l = new LinkedList<TreeNode>();
        l.add(root);
        int nums = 1;   //当前层结点的个数
        while(nums != 0){ //每层一次
            deepth++;
            int nextNums = 0;//下一层结点的个数
            for(int i = 0; i < nums; i++){
                TreeNode node = l.removeFirst();
                if(node.left != null){
                    nextNums++;
                    l.add(node.left);
                }
                if(node.right != null){
                    nextNums++;
                    l.add(node.right);
                }
            }
            nums = nextNums;
        }
        return deepth;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
}
